package leetcode_day._2021._202110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/10/15 19:57
 * 外观数列
 * 给定一个正整数 n ，输出外观数列的第 n 项。
 * 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
 * 你可以将其视作是由递归公式定义的数字字符串序列：
 * countAndSay(1) = "1"
 * countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串
 * 算法：模拟
 */
public class _15_38 {
    public static void main(String[] args) {
        System.out.println(new _15_38().countAndSay(4));
    }

    static String[] ans;
    static {
        ans = new String[30];
        ans[0] = "1";
        ans[1] = "11";
        for (int i = 2; i <= 29; i++) {
            String tmp = ans[i - 1];
            StringBuilder sb = new StringBuilder();
            int cnt = 1;
            for (int j = 1; j < tmp.length(); j++) {
                if (j == tmp.length() - 1) {
                    if (tmp.charAt(j) == tmp.charAt(j - 1))
                        sb.append(cnt + 1).append(tmp.charAt(j));
                    else sb.append(cnt).append(tmp.charAt(j - 1))
                            .append(1).append(tmp.charAt(j));
                    break;
                }
                if (tmp.charAt(j) != tmp.charAt(j - 1)) {
                    sb.append(cnt).append(tmp.charAt(j - 1));
                    cnt = 1;
                } else ++cnt;
            }
            ans[i] = sb.toString();
        }
    }
    static {
        ans = new String[30];
        ans[0] = "1";
        for (int i = 1; i < 30; i++) {
            String pre = ans[i - 1], cur = "";
            int len = pre.length();
            for (int j = 0; j < len; ) {
                int k = j + 1;
                while (k < len && pre.charAt(k) == pre.charAt(j)) ++k;
                int cnt = k - j;
                cur += cnt + "" + pre.charAt(j);
                j = k;
            }
            ans[i] = cur;
        }
    }

    public String countAndSay(int n) {
        return ans[n - 1];
    }

}
